#include "Grammar.h"
#include "ParseTableBuilder.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

// 词法符号结构
struct Symbol
{
    string type; // 词法类别，比如 "int", "Ident", "=", "EOF"
    string text; // 原始文本
    string code;
};

// 读取token流（词法分析器输出）
vector<Symbol> loadTokens(const string &filename)
{
    vector<Symbol> tokens;
    ifstream fin(filename);
    if (!fin)
    {
        cerr << "无法打开文件: " << filename << endl;
        return tokens;
    }
    string word, tokenTypeValue;
    while (fin >> word >> tokenTypeValue)
    {
        size_t start = tokenTypeValue.find('<');
        size_t comma = tokenTypeValue.find(',');
        size_t end = tokenTypeValue.find('>');
        if (start == string::npos || comma == string::npos || end == string::npos)
            continue;
        string type = tokenTypeValue.substr(start + 1, comma - start - 1);
        string val = tokenTypeValue.substr(comma + 1, end - comma - 1);
        tokens.push_back({type, word, val});
    }
    fin.close();
    tokens.push_back({"EOF", "$", "$"}); // 添加终结符EOF方便分析结束判断
    return tokens;
}

// 判断符号是否为终结符
bool isTerminal(const string &symbol, const Grammar &g)
{
    return g.isTerminal(symbol);
}

// 打印当前分析动作
void printAction(int step, const string &stackTop, const Symbol &curToken, const string &action)
{
    cout << step << "\t" << stackTop << " # " << curToken.text << "\t" << action << endl;
}

string mapTokenTypeToTerminal(const Symbol &token)
{
    if (token.type == "KW") // 关键字
    {
        // 关键字直接用词文本对应终结符
        if (token.text == "int")
            return "int";
        if (token.text == "void")
            return "void";
        if (token.text == "return")
            return "return";
        if (token.text == "const")
            return "const";
        if (token.text == "if")
            return "if";
        if (token.text == "else")
            return "else";
        if (token.text == "float")
            return "float";
        if (token.text == "main")
            return "Ident";
        // 可以继续补充其他关键字
    }
    else if (token.type == "IDN") // 标识符
    {
        return "Ident";
    }
    else if (token.type == "INT") // 整数常量
    {
        return "IntConst";
    }
    else if (token.type == "FLOAT") // 浮点常量
    {
        return "FloatConst";
    }
    else if (token.type == "OP") // 运算符
    {
        // 运算符直接用文本，比如 "+", "-", "=" 等
        return token.text;
    }
    else if (token.type == "SE") // 分隔符，可能是括号、分号等
    {
        // 这里用token.text，因为token文本就是符号
        // 例如 "("、")"、";"、","、"{"、"}" 等
        return token.text;
    }
    else if (token.type == "EOF")
    {
        return "EOF";
    }

    // 其他未识别的token类型，返回type方便调试
    return token.type;
}

// 添加超前查看函数来区分声明和函数定义
bool isNextTokenLeftParen(const vector<Symbol> &tokens, size_t currentIndex)
{
    if (currentIndex + 1 < tokens.size())
    {
        string nextTerminal = mapTokenTypeToTerminal(tokens[currentIndex + 1]);
        cout << "判断是否是函数" << (nextTerminal == "(");
        return nextTerminal == "(";
    }
    return false;
}

int main()
{

    ofstream fout("output.tsv");
    if (!fout.is_open())
    {
        cerr << "无法打开输出文件 output.tsv" << endl;
        return 1;
    }

    // 保存原 cout 缓冲区
    streambuf *oldCoutBuf = cout.rdbuf();
    cout.rdbuf(fout.rdbuf()); // 重定向 cout 到文件

    Grammar g;

    // 设置终结符
    g.setTerminals({"int", "void", "return", "const", "main", "float", "if", "else",
                    "+", "-", "*", "/", "%", "=", ">", "<", "==", "<=", ">=", "!=", "&&", "||",
                    "(", ")", "{", "}", ";", ",",
                    "Ident", "IntConst", "FloatConst", "EOF"});

    // 根据C--文法添加产生式
    // 1. Program -> compUnit
    g.addProduction("Program", {"compUnit"});

    // 2. compUnit -> (decl | funcDef)* EOF
    // 为了处理*(星号闭包)，我们需要展开为递归形式
    g.addProduction("compUnit", {"EOF"}); // 空的情况
    g.addProduction("compUnit", {"funcOrDecl", "compUnit"});

    g.addProduction("funcOrDecl", {"funcDef"});
    g.addProduction("funcOrDecl", {"decl"});

    // 3. decl -> constDecl | varDecl
    g.addProduction("decl", {"constDecl"});
    g.addProduction("decl", {"varDecl"});

    // 4. constDecl -> 'const' bType constDef (',' constDef)* ';'
    // 展开(',' constDef)*
    g.addProduction("constDecl", {"const", "bType", "constDef", "constDefList", ";"});
    g.addProduction("constDefList", {}); // epsilon
    g.addProduction("constDefList", {",", "constDef", "constDefList"});

    // 5. bType -> 'int' | 'float'
    g.addProduction("bType", {"int"});
    g.addProduction("bType", {"float"});

    // 6. constDef -> Ident '=' constInitVal
    g.addProduction("constDef", {"Ident", "=", "constInitVal"});

    // 7. constInitVal -> constExp
    g.addProduction("constInitVal", {"constExp"});

    // 8. varDecl -> bType varDef (',' varDef)* ';'
    g.addProduction("varDecl", {"bType", "varDef", "varDefList", ";"});
    g.addProduction("varDefList", {}); // epsilon
    g.addProduction("varDefList", {",", "varDef", "varDefList"});

    // 9. varDef -> Ident | Ident '=' initVal
    g.addProduction("varDef", {"Ident", "initOpt"});
    g.addProduction("initOpt", {}); // epsilon
    g.addProduction("initOpt", {"=", "initVal"});

    // 10. initVal -> exp
    g.addProduction("initVal", {"exp"});

    // 11. funcDef -> funcType Ident '(' (funcFParams)? ')' block
    g.addProduction("funcDef", {"funcType", "Ident", "(", "funcFParamsOpt", ")", "block"});
    g.addProduction("funcFParamsOpt", {}); // epsilon
    g.addProduction("funcFParamsOpt", {"funcFParams"});

    // 12. funcType -> 'void' | 'int' | 'float'
    g.addProduction("funcType", {"void"});
    g.addProduction("funcType", {"int"});
    g.addProduction("funcType", {"float"});

    // 13. funcFParams -> funcFParam (',' funcFParam)*
    g.addProduction("funcFParams", {"funcFParam", "funcFParamList"});
    g.addProduction("funcFParamList", {}); // epsilon
    g.addProduction("funcFParamList", {",", "funcFParam", "funcFParamList"});

    // 14. funcFParam -> bType Ident
    g.addProduction("funcFParam", {"bType", "Ident"});

    // 15. block -> '{' (blockItem)* '}'
    g.addProduction("block", {"{", "blockItemList", "}"});
    g.addProduction("blockItemList", {}); // epsilon
    g.addProduction("blockItemList", {"blockItem", "blockItemList"});

    // 16. blockItem -> decl | stmt
    g.addProduction("blockItem", {"decl"});
    g.addProduction("blockItem", {"stmt"});

    // 17. stmt -> lVal '=' exp ';' | (exp)? ';' | block | 'if' '(' cond ')' stmt ('else' stmt)? | 'return' (exp)? ';'
    g.addProduction("stmt", {"lVal", "=", "exp", ";"});
    // g.addProduction("stmt", {"exp", ";"});
    g.addProduction("stmt", {
                                ";",
                            }); // 空语句
    g.addProduction("stmt", {"block"});
    g.addProduction("stmt", {"if", "(", "cond", ")", "stmt", "elseOpt"});
    g.addProduction("stmt", {"return", "expOpt", ";"});

    g.addProduction("expOpt", {}); // epsilon
    g.addProduction("expOpt", {"exp"});
    g.addProduction("elseOpt", {}); // epsilon
    g.addProduction("elseOpt", {"else", "stmt"});

    // 18. exp -> addExp
    g.addProduction("exp", {"addExp"});
    g.addProduction("exp", {"lOrExp"}); // for test

    // 19. cond -> lOrExp
    g.addProduction("cond", {"lOrExp"});

    // 20. lVal -> Ident
    g.addProduction("lVal", {"Ident"});

    // 21. primaryExp -> '(' exp ')' | lVal | number
    g.addProduction("primaryExp", {"(", "exp", ")"});
    g.addProduction("primaryExp", {"lVal"});
    g.addProduction("primaryExp", {"number"});

    // 22. number -> IntConst | FloatConst
    g.addProduction("number", {"IntConst"});
    g.addProduction("number", {"FloatConst"});

    // 23. unaryExp -> primaryExp | Ident '(' (funcRParams)? ')' | unaryOp unaryExp
    g.addProduction("unaryExp", {"primaryExp"});
    // g.addProduction("unaryExp", {"Ident", "(", "funcRParamsOpt", ")"}); // 情况不对请注释
    g.addProduction("unaryExp", {"unaryOp", "unaryExp"});

    g.addProduction("funcRParamsOpt", {}); // epsilon
    g.addProduction("funcRParamsOpt", {"funcRParams"});

    // 24. unaryOp -> '+' | '-' | '!'
    g.addProduction("unaryOp", {"+"});
    g.addProduction("unaryOp", {"-"});
    g.addProduction("unaryOp", {"!"});

    // 25. funcRParams -> funcRParam (',' funcRParam)*
    g.addProduction("funcRParams", {"funcRParam", "funcRParamList"});
    g.addProduction("funcRParamList", {}); // epsilon
    g.addProduction("funcRParamList", {",", "funcRParam", "funcRParamList"});

    // 26. funcRParam -> exp
    g.addProduction("funcRParam", {"exp"});

    // 27. mulExp -> unaryExp | mulExp ('*' | '/' | '%') unaryExp
    // 消除左递归: mulExp -> unaryExp mulExpRest
    g.addProduction("mulExp", {"unaryExp", "mulExpRest"});
    g.addProduction("mulExpRest", {}); // epsilon
    g.addProduction("mulExpRest", {"*", "unaryExp", "mulExpRest"});
    g.addProduction("mulExpRest", {"/", "unaryExp", "mulExpRest"});
    g.addProduction("mulExpRest", {"%", "unaryExp", "mulExpRest"});

    // 28. addExp -> mulExp | addExp ('+' | '-') mulExp
    // 消除左递归: addExp -> mulExp addExpRest
    g.addProduction("addExp", {"mulExp", "addExpRest"});
    g.addProduction("addExpRest", {}); // epsilon
    g.addProduction("addExpRest", {"+", "mulExp", "addExpRest"});
    g.addProduction("addExpRest", {"-", "mulExp", "addExpRest"});

    // 29. relExp -> addExp | relExp ('<' | '>' | '<=' | '>=') addExp
    // 消除左递归: relExp -> addExp relExpRest
    g.addProduction("relExp", {"addExp", "relExpRest"});
    g.addProduction("relExpRest", {}); // epsilon
    g.addProduction("relExpRest", {"<", "addExp", "relExpRest"});
    g.addProduction("relExpRest", {">", "addExp", "relExpRest"});
    g.addProduction("relExpRest", {"<=", "addExp", "relExpRest"});
    g.addProduction("relExpRest", {">=", "addExp", "relExpRest"});

    // 30. eqExp -> relExp | eqExp ('==' | '!=') relExp
    // 消除左递归: eqExp -> relExp eqExpRest
    g.addProduction("eqExp", {"relExp", "eqExpRest"});
    g.addProduction("eqExpRest", {}); // epsilon
    g.addProduction("eqExpRest", {"==", "relExp", "eqExpRest"});
    g.addProduction("eqExpRest", {"!=", "relExp", "eqExpRest"});

    // 31. lAndExp -> eqExp | lAndExp '&&' eqExp
    // 消除左递归: lAndExp -> eqExp lAndExpRest
    g.addProduction("lAndExp", {"eqExp", "lAndExpRest"});
    g.addProduction("lAndExpRest", {}); // epsilon
    g.addProduction("lAndExpRest", {"&&", "eqExp", "lAndExpRest"});

    // 32. lOrExp -> lAndExp | lOrExp '||' lAndExp
    // 消除左递归: lOrExp -> lAndExp lOrExpRest
    g.addProduction("lOrExp", {"lAndExp", "lOrExpRest"});
    g.addProduction("lOrExpRest", {}); // epsilon
    g.addProduction("lOrExpRest", {"||", "lAndExp", "lOrExpRest"});

    // 33. constExp -> addExp
    g.addProduction("constExp", {"addExp"});

    // 计算FIRST集合
    g.computeFirst();

    // 打印FIRST集合
    // g.printFirst();

    // 计算并打印 FOLLOW 集合
    g.computeFollow("Program"); // Program 是起始符号
                                // g.printFollow();

    // return 0;

    ParseTableBuilder builder(g);
    builder.build();
    // builder.print();

    auto parseTable = builder.getTable();

    // 读取词法分析器token输出
    vector<Symbol> tokens = loadTokens("token.tsv");
    if (tokens.empty())
    {
        cerr << "无输入token，程序退出" << endl;
        return 1;
    }

    // 预测分析过程
    stack<string> parseStack;
    parseStack.push("Program"); // 初始符号

    size_t index = 0; // token游标
    int step = 1;

    while (!parseStack.empty())
    {
        string top = parseStack.top();
        Symbol cur = tokens[index];
        string curTerminal = mapTokenTypeToTerminal(cur);

        if (top == "funcOrDecl")
        {
            // 需要向前看更多token来做判断
            // 寻找类型关键字后的标识符及其后续符号
            size_t lookAhead = index;
            // cout<<tokens[lookAhead].type<<" "<<tokens[lookAhead].text<<endl;

            // 跳过类型关键字 (int/void/float 或 const bType)
            if (tokens[lookAhead].type == "KW" &&
                (tokens[lookAhead].text == "const"))
            {
                lookAhead++; // 跳过const
                if (lookAhead < tokens.size())
                    lookAhead++; // 跳过bType
            }
            else if (tokens[lookAhead].type == "KW" &&
                     (tokens[lookAhead].text == "int" ||
                      tokens[lookAhead].text == "void" ||
                      tokens[lookAhead].text == "float"))
            {
                lookAhead++; // 跳过类型
            }

            // 现在应该是标识符
            // cout<<tokens[lookAhead].type<<" "<<tokens[lookAhead].text<<endl;
            if (lookAhead < tokens.size() && tokens[lookAhead].type == "IDN" || tokens[lookAhead].text == "main")
            {
                lookAhead++; // 跳过标识符
                // 检查标识符后面是什么
                if (lookAhead < tokens.size() &&
                    mapTokenTypeToTerminal(tokens[lookAhead]) == "(")
                {
                    //printAction(step++, top, cur, "reduction to funcDef");
                    parseStack.pop();
                    parseStack.push("funcDef");
                }
                else
                {
                    //printAction(step++, top, cur, "reduction to decl");
                    parseStack.pop();
                    parseStack.push("decl");
                }
            }
            else
            {
                // 默认处理为声明
                //printAction(step++, top, cur, "reduction to decl");
                parseStack.pop();
                parseStack.push("decl");
            }
            continue;
        }

        // 这里打一个补丁看看行不行 for 函数调用
        if (top == "primaryExp" && curTerminal == "Ident")
        {
            // 向前看下一个符号
            if (index + 1 < tokens.size() &&
                mapTokenTypeToTerminal(tokens[index + 1]) == "(")
            {
                // 这是函数调用，手动构造调用序列
                //printAction(step++, top, cur, "reduction to function call");
                printAction(step++, top, cur, "reduction");
                parseStack.pop();
                // 按 Ident ( funcRParamsOpt ) 的顺序入栈
                parseStack.push(")");
                if (index + 2 < tokens.size() && // 补丁+，意在解决空参数调用
                    mapTokenTypeToTerminal(tokens[index + 2]) != ")")
                    parseStack.push("funcRParamsOpt");
                parseStack.push("(");
                parseStack.push("Ident");
            }
            else
            {
                // 普通变量，走正常的 primaryExp -> lVal 路径
                // printAction(step++, top, cur, "reduction to lVal");
                printAction(step++, top, cur, "reduction");
                parseStack.pop();
                parseStack.push("lVal"); // 推入 lVal
            }
            continue;
        }

        // 补丁++ 无返回值的调用
        if (top == "stmt" && curTerminal == "Ident")
        {
            if (index + 1 < tokens.size() &&
                mapTokenTypeToTerminal(tokens[index + 1]) == "(")
            {
                // 函数调用作为语句
                //printAction(step++, top, cur, "reduction to exp ;");
                printAction(step++, top, cur, "reduction");
                parseStack.pop();
                parseStack.push(";");
                parseStack.push("exp");
                continue;
            }
        }

        if (top == "funcRParamList" && curTerminal == ")")
        {
            //printAction(step++, top, cur, "reduction to epsilon");
            printAction(step++, top, cur, "reduction");
            parseStack.pop();
            continue;
        }

        // 补丁结束

        if (isTerminal(top, g))
        {
            if (top == curTerminal)
            {
                printAction(step++, top, cur, "move");
                parseStack.pop();
                index++;
            }
            else
            {
                cerr << "error！期待符号 " << top << "，但遇到 " << curTerminal << endl;
                return 1;
            }
        }
        else
        {
            if (parseTable.count(top) == 0 || parseTable[top].count(curTerminal) == 0)
            {
                cerr << "error！无匹配产生式，非终结符 " << top << "，输入符号 " << curTerminal << endl;
                return 1;
            }
            auto prod = parseTable[top][curTerminal];
            // printAction(step++, top, cur, "reduce by " + top + " ->");
            printAction(step++, top, cur, "reduction");
            // for (const auto &sym : prod)
            //     cout << " " << sym;
            // cout << endl;

            parseStack.pop();
            if (!(prod.size() == 1 && prod[0] == "ε"))
            {
                for (auto it = prod.rbegin(); it != prod.rend(); ++it)
                {
                    parseStack.push(*it);
                }
            }
        }
    }

    // 栈空且token扫描完毕即接受
    if (index == tokens.size())
    {
        cout << step << "\t$\taccept" << endl;
        // cout << "语法分析成功！" << endl;
    }
    else
    {
        cerr << "error" << endl;
        return 1;
    }

    cout.rdbuf(oldCoutBuf);
    fout.close();

    cout << "输出已保存到 output.tsv" << endl;

    return 0;
}